package algorithm.tanxin;

import java.util.HashSet;

public class Light {


    public static int minLight1(String road) {
        if(road == null || road.length() == 0)
            return 0;
        return process(road.toCharArray(), 0, new HashSet<>());
    }

    public static int process(char[] road, int index, HashSet<Integer> lights){
        if(index == road.length){
            for (int i = 0; i < road.length; i++) {
                if(road[i] == '.'){
                    if(!lights.contains(i-1) && !lights.contains(i) && !lights.contains(i+1))
                       return Integer.MAX_VALUE;
                }
            }
            return lights.size();
        }

        int no = process(road, index + 1, lights);
        int yes = Integer.MAX_VALUE;
        if(road[index] == '.'){
            lights.add(index);
            yes = process(road, index + 1, lights);
            lights.remove(index);
        }
        return Math.min(no, yes);
    }

    public static int minLight2(String road){
        if(road == null || road.length() == 0)
            return 0;

        char[] str = road.toCharArray();
        int lights = 0;
        int index = 0;
        while(index < str.length){
            if(str[index] == 'X'){
                index++;
            }else{
                lights++;
                if(index == str.length - 1)
                    return lights;
                if(str[index + 1] == 'X')
                   index = index + 2;
                else{
                    index = index + 3;
                }
            }
        }
        return lights;
    }

    // for test
    public static String randomString(int len) {
        char[] res = new char[(int) (Math.random() * len) + 1];
        for (int i = 0; i < res.length; i++) {
            res[i] = Math.random() < 0.5 ? 'X' : '.';
        }
        return String.valueOf(res);
    }

    public static void main(String[] args) {
        int len = 20;
        int testTime = 100000;
        for (int i = 0; i < testTime; i++) {
            String test = randomString(len);
            int ans1 = minLight1(test);
            int ans2 = minLight2(test);
            if (ans1 != ans2) {
                System.out.println("oops!");
            }
        }
        System.out.println("finish!");
    }

}
